/***************************************************************************
 *   Copyright (C) 2007 by Warren Kenny   				   *
 *   warren.kenny@gmail.com   						   *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/
 

template< class T > inline
gsLinkedList<T>::gsLinkedList() :
m_head( GS_NULL ),
m_tail( GS_NULL ),
m_size( 0 ),
m_history( GS_NULL ),
m_historyIndex( 0 )
{}


template< class T > inline
gsLinkedList<T>::gsLinkedList( const gsLinkedList<T>& other ) :
m_head( GS_NULL ),
m_tail( GS_NULL ),
m_history( GS_NULL )
{
	(*this) = other;
}


template< class T > inline
gsLinkedList<T>::gsLinkedList( const gsContainer<T>& container )
{
	(*this) = container;
}


template< class T > inline
gsBool gsLinkedList<T>::insert( const T& object )
{
	gsLink<T>* link = new gsLink<T>( object );
	
	if( m_head == GS_NULL )
	{
		m_head = m_tail = link;
		m_head->setLinks( m_tail, m_tail );
		m_tail->setLinks( m_head, m_head );
	}
	else
	{
		m_tail->setNext( link );
		m_head->setPrevious( link );
		link->setLinks( m_tail, m_head );
		m_tail = link;
	}
	
	m_size++;
}


template< class T > inline
gsBool gsLinkedList<T>::remove( const T& object )
{
	gsBool found = false;
	
	if( m_head && m_tail )
	{
		gsLink<T>* temp = m_head;
		
		for( gsUInt i = 0; ( ( i < m_size ) && ( !found ) ); i++ )
		{
			if( temp->get() == object )
			{
				found = true;
				removeLink( temp );
			}
			else
			{
				temp = temp->next();
			}
		}
	}
	
	return found;
}


template< class T > inline
gsBool gsLinkedList<T>::find( const T& object )
{
	gsBool found = false;
	
	if( m_head && m_tail )
	{
		gsLink<T>* temp = m_head;
		
		for( gsUInt i = 0; ( ( i < m_size ) && ( !found ) ); i++ )
		{
			if( temp->get() == object )
			{
				found = true;
			}
			
			temp = temp->next();
		}
	}
	
	return found;
	
	
}


template< class T > inline
gsBool gsLinkedList<T>::get( const gsUInt index, T& object )
{
	gsBool retrieved = true;
	
	if( index < 0 || index >= m_size )
	{
		retrieved = false;
	}
	else
	{
		object = (*this)[index];
	}
	
	return retrieved;
}


template< class T > inline
gsBool gsLinkedList<T>::empty()
{
	return m_size == 0;
}


template< class T > inline
const gsUInt gsLinkedList<T>::getSize()
{
	return m_size;
}


template< class T > inline
const gsUInt gsLinkedList<T>::getCapacity()
{
	return m_size;
}


template< class T > inline
void gsLinkedList<T>::clear()
{
	if( m_head && m_tail )
	{
		gsLink<T>* current = m_head;
		gsLink<T>* next = current->next();
		
		while( current != m_tail )
		{
			delete current;
			current = GS_NULL;	
			
			current = next;
			next = next->next();
		}
		
		delete current;
		current = GS_NULL;
	}
		
}


template< class T > inline
gsLink<T>* gsLinkedList<T>::getLink( const gsUInt index )
{
	gsLink<T>* target = m_head; 
	
	if( m_history )
	{
		if( index == m_historyIndex )
		{
			target = m_history;
		}
		else if( index == ( m_historyIndex + 1 ) )
		{
			target = m_history->next();
		}
		else if( index == ( m_historyIndex - 1 ) )
		{
			target = m_history->previous();
		}
		else
		{
			for( gsUInt i = 0; i < index; i++ )
			{
				target = target->next();
			}
		}
	}
	else
	{
		for( gsUInt i = 0; i < index; i++ )
		{
			target = target->next();
		}
	}
	
	m_history = target;
	m_historyIndex = index;
	
	return target;
}


template< class T > inline
void gsLinkedList<T>::removeLink( gsLink<T>* target )
{
	if( target == m_head )
	{
		target->next()->setPrevious( target->previous() );
		target->previous()->setNext( target->next() );
		m_head = target->next();
	}
	else if( target == m_tail )
	{
		target->next()->setPrevious( target->previous() );
		target->previous()->setNext( target->next() );
		m_tail = target->next();
	}
	
	if( m_history == target )
	{
		m_history = m_head;
		m_historyIndex = 0;
	}
	
	delete target;
	
	m_size--;
}

template< class T > inline
gsLinkedList<T>& gsLinkedList<T>::operator=( gsLinkedList<T>& other )
{
	clear();
	
	m_size = other.m_size;
	m_historyIndex = other.m_historyIndex;
	
	for( gsUInt i = 0; i < m_size; i++ )
	{
		T temp = other[i];
				
		if( i == other.m_historyIndex )
		{
			gsLink<T>* link = new gsLink<T>( temp );
			m_history = link;
		}
		
		insert( temp );
	}
}


template< class T > inline
gsLinkedList<T>& gsLinkedList<T>::operator=( gsContainer<T>& container )
{
	clear();
	
	m_historyIndex = 0;
	m_history = GS_NULL;
	
	for( gsUInt i = 0; i < container.getSize(); i++ )
	{
		T temp;
		
		if( get( i, temp ) )
		{
			insert( temp );
		}
	}
}


template< class T > inline
gsBool gsLinkedList<T>::operator==( gsLinkedList<T>& other )
{
	gsBool identical = true;
	
	if( m_size != other.m_size )
	{
		identical = false;
	}
	else
	{
		gsBool discrepancy = false;
		
		for( gsUInt i = 0; ( i < m_size && identical ); i++ )
		{
			if( other[i] != (*this)[i] )
			{
				identical = false;
			}
		}
	}
	
	return identical;
}


template< class T > inline
gsBool gsLinkedList<T>::operator==( gsContainer<T>& container )
{
	gsBool identical = true;
	
	if( m_size != container.getSize() )
	{
		identical = false;
	}
	else
	{
		gsBool discrepancy = false;
		
		for( gsUInt i = 0; ( i < m_size && identical ); i++ )
		{
			T temp;
			
			if( container.get( i, temp ) )
			{
				if( temp != (*this)[i] )
				{
					identical = false;
				}
			}
		}
	}
	
	return identical;
}


template< class T > inline
T& gsLinkedList<T>::operator[]( const gsUInt index ) throw( gsArrayIndexOutOfBoundsException )
{
	if( index < 0 || index >= m_size )
	{
		gsArrayIndexOutOfBoundsException exception;
		throw exception;
	}
	else
	{
		gsLink<T>* target = getLink( index );
		return target->get();
	}
}


template< class T > inline
const T& gsLinkedList<T>::operator[]( const gsUInt index ) const throw( gsArrayIndexOutOfBoundsException )
{
	if( index < 0 || index >= m_size )
	{
		gsArrayIndexOutOfBoundsException exception;
		throw exception;
	}
	else
	{
		gsLink<T>* target = getLink( index );
		return target->get();
	}
}


template< class T > inline
gsLinkedList<T>::~gsLinkedList()
{
	clear();
}